package sort;

/**
 * 希尔排序
 *
 * @param <T>
 * @author zj
 */
@SuppressWarnings("unchecked")
public class ShellSort<T extends Comparable<T>> implements Sort<T> {
    @Override
    public void sort(T[] arr) {
        if (arr == null || arr.length == 0) {
            return;
        }
        int d = arr.length / 2;
        T temp;
        while (d > 0) {
            for (int i = d; i < arr.length; i++) {
                int j = i - d;
                temp = arr[i];
                while (j >= 0 && temp.compareTo(arr[j]) < 0) {
                    arr[j + d] = arr[j];
                    j = j - d;
                }
                arr[j + d] = temp;
            }
            d = d / 2;
        }
    }
}
